package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         15,
		Discription: "三数之和",
		Level:       2,
		Labels: map[string]int{
			"双指针滑动": 1,
			"排序":    1,
			"去重":    1,
		},
	})
}

func ThreeSum(nums []int) [][]int {
	n := len(nums)
	//排序一是为了后续双指针滑动，二是为了避免重复
	sort.Ints(nums)
	res := make([][]int, 0)
	for i := 0; i <= n-3; i++ {
		//避免重复
		for i > 0 && i <= n-3 && nums[i] == nums[i-1] {
			i++
		}

		left := i + 1
		right := n - 1
		for left < right {
			sum := nums[left] + nums[right] + nums[i]
			if sum == 0 {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				//避免重复
				left++
				for left < right && nums[left] == nums[left-1] {
					left++
				}
				//避免重复
				right--
				for left < right && nums[right] == nums[right+1] {
					right--
				}
				continue
			}

			if sum > 0 {
				//避免重复
				right--
				for left < right && nums[right] == nums[right+1] {
					right--
				}
			} else {
				//避免重复
				left++
				for left < right && nums[left] == nums[left-1] {
					left++
				}
			}
		}
	}

	return res
}
